#include <vector>
#include <exception>
#include <iostream>

using namespace std;

typedef exception BadIterator;  //This is a simplification of the exception class.  In a real implementation care would be taken to return the right error message.

template <class Object>
class LList;     // Incomplete declaration.

template <class Object>
class LListItr;  // Incomplete declaration.

// LListNode class
template <class Object>
class LListNode
{
        LListNode( const Object & theElement = Object( ),
                        LListNode * n = NULL )
                : element( theElement ), next( n ) { }

        Object     element;
        LListNode *next;

        friend class LList<Object>;
        friend class LListItr<Object>;
};

// LList class
template <class Object>
class LList
{
        public:
                LList( );
                ~LList( );

                bool isEmpty( ) const;
                void makeEmpty( );

                LListItr<Object> first( ) const;
                LListItr<Object> zeroth( ) const;

                void remove( const Object & x);
                LListItr<Object> findPrevious( const Object & x ) const;
                void insert( const Object & x, const LListItr<Object> & p );

                void push_front(const Object& obj);
                void pop_front();
                size_t size() const;
                void reverse();
                void unique();

        private:
                LListNode<Object> *header;
                size_t items;
};


// LListItr class
template <class Object>
class LListItr
{
        public:
                LListItr( ) : current( NULL ) { }

                void operator++( );
                Object & operator*( ) const;
                bool operator==(LListItr<Object> rhs) const;
                bool operator!=(LListItr<Object> rhs) const;

                bool isPastEnd( ) const
                { return current == NULL; }

        private:
                LListNode<Object> *current;    // Current position

                LListItr( LListNode<Object> *theNode )
                        : current( theNode ) { }

                friend class LList<Object>; // Grant access to constructor
};

// increment
template <class Object>
void LListItr<Object>::operator++(){
        current = current->next;
}

//deref
template <class Object>
Object& LListItr<Object>::operator*()const{
        return current->element;
}

//equality
template <class Object>
bool LListItr<Object>::operator==(LListItr<Object> rhs) const {
        return current == rhs.current;
}

template <class Object>
bool LListItr<Object>::operator!=(LListItr<Object> rhs) const {
        return current != rhs.current;
}

// Construct the list.
        template <class Object>
LList<Object>::LList( )
{
        items = 0;
        header = new LListNode<Object>;
}

// Destructor.
        template <class Object>
LList<Object>::~LList( )
{
        makeEmpty( );
        delete header;
}

// Test if the list is logically empty.
// Return true if empty, false, otherwise.
template <class Object>
bool LList<Object>::isEmpty( ) const
{
        return header->next == NULL;
}

// Make the list logically empty.
        template <class Object>
void LList<Object>::makeEmpty( )
{
        while( !isEmpty( ) )
                remove( *first( ) );
        items = 0;
}

// Return an iterator representing the header node.
template <class Object>
LListItr<Object> LList<Object>::zeroth( ) const
{
        return LListItr<Object>( header );
}

// Return an iterator representing the first node in the list.
// This operation is valid for empty lists.
template <class Object>
LListItr<Object> LList<Object>::first( ) const
{
        return LListItr<Object>( header->next );
}

// Insert item x after p.
        template <class Object>
void LList<Object>::insert( const Object & x, const LListItr<Object> & p )
{
        if( p.current != NULL )
        {
                p.current->next = new LListNode<Object>( x, p.current->next );
        }
        items++;
}

// Remove the first occurrence of an item x.
        template <class Object>
void LList<Object>::remove( const Object & x )
{
        LListNode<Object> *p = findPrevious( x ).current;

        if( p->next != NULL )
        {
                LListNode<Object> *oldNode = p->next;
                p->next = p->next->next;  // Bypass deleted node
                delete oldNode;
        }
        items--;
}

// Return iterator prior to the first node containing an item x.
template <class Object>
LListItr<Object> LList<Object>::findPrevious( const Object & x ) const
{
        LListNode<Object> *p = header;

        while( p->next != NULL && p->next->element != x )
                p = p->next;

        return LListItr<Object>( p );
}

//********************************************** ACTUAL HW 3B *************************************************

template<class Object>
class Stack{
	LList<Object> data;
public:
	void push(const Object& o){
		data.push_front(o);
	}
	void pop(){
		data.pop_front();
	}
	Object& top(){
		return *(data.first());
	}
	void swap(const Object& o){
		data.pop_front();
		data.push_front(o);
	}
	size_t size()const{
		return data.size();
	}
	bool empty()const{
		data.isEmpty();
	}
};
